home *** CD-ROM | disk | FTP | other *** search
/ Amiga Format CD 52 / Amiga Format AFCD52 (Issue 136, May 2000).iso / -serious- / programming / c / stormamiga_lib-v45_00d / stormc_v3-examples / standard / pi / pi.c < prev   
C/C++ Source or Header  |  2000-02-28  |  3KB  |  155 lines
  1. /*
  2.  
  3. Programm für den Tröpfel-Algorithmus von PI
  4.  
  5. Algorithmus aus: Spektrum der Wissenschaft 12/1995, Mathematische Unterhaltungen
  6.  
  7. Originalversion von: Martin Knapmeyer, 03.01.1996
  8.  
  9. Umsetzung nach StormC: HAAGE & PARTNER GmbH, 16.02.1996
  10.  
  11. Mit 32 bit Integers kann man auch sehr viele Dezimalen berechnen, mit 16 bit
  12. Integers wäre 10000 Dezimalen etwa die Grenze.
  13.  
  14. Allerdings hat der Algorithmus quadratische Ordnung: doppelte Anzahl Stellen,
  15. vierfache Zeit. Schon 10000 Stellen brauchen auf einem A3000 etwa 2 Stunden.
  16.  
  17. */
  18.  
  19. #include <stdio.h>
  20. #include <stdlib.h>
  21. #include <time.h>
  22.  
  23.  
  24. int n; // Anzahl der Nachkommastellen
  25. int klen;
  26.  
  27. int *result; // Zeiger auf ein Feld mit n int
  28. int *chain;  // Zeiger auf ein Feld mit klen == 10 * n / 3 int
  29. int *temp;   // Zeiger auf ein Feld mit n int
  30.  
  31. #ifndef NDEBUG
  32. void write_chain(void)
  33. {
  34.   int i;
  35.   for (i = 0; i < klen; i++)
  36.     printf("%ld ",chain[i]);
  37.   printf("\n");
  38. }
  39. #endif
  40.  
  41. void write_result(void)
  42. {
  43.   int i;
  44.   printf("PI:\n");
  45.   for (i = 1; i < n; i++)
  46.   {
  47.     printf("%ld",result[i]);
  48.     if (i % 50 == 0)
  49.       printf("\n");
  50.   };
  51.   printf("\n");
  52. }
  53.  
  54. void init_chain(void)
  55. {
  56.   int i;
  57.   for (i = 0; i < klen; i++)
  58.     chain[i] = 2;
  59. }
  60.  
  61. void drop(void)
  62. {
  63.   int vcnt = 0, ecnt = 0;
  64.   int i,j;
  65.   div_t qr;
  66.   for (i = 0; i < n; i++)
  67.   {
  68.     for (j = 0; j < klen; j++)
  69.       chain[j] *= 10;
  70.     for (j = klen - 1; j >= 1; j--)
  71.     {
  72.       qr = div(chain[j],(2*j + 1));
  73.       chain[j] = qr.rem;
  74.       chain[j - 1] += qr.quot*j;
  75.     };
  76.     qr = div(chain[0],10);
  77.     chain[0] = qr.rem;
  78.     if (qr.quot != 9 && qr.quot != 10)
  79.     {
  80.       for (j = 0; j <= vcnt; j++)
  81.       {
  82.     #ifndef NDEBUG
  83.       printf("%ld. Stelle: %ld\n",ecnt-1,temp[j]);
  84.     #endif
  85.     result[ecnt] = temp[j];
  86.     ecnt++;
  87.     temp[j] = 0;
  88.       };
  89.       vcnt = 0;
  90.       temp[vcnt] = qr.quot;
  91.     }
  92.     else
  93.     {
  94.       if (qr.quot == 9)
  95.       {
  96.     vcnt++;
  97.     temp[vcnt] = qr.quot;
  98.       }
  99.       else // if (qr.quot == 10)
  100.       {
  101.     qr.quot = 1;
  102.     for (j = vcnt; j >= 0; j--)
  103.     {
  104.       temp[j] += qr.quot;
  105.       qr = div(temp[j],10);
  106.       temp[j] = qr.rem;
  107.     };
  108.     for (j = 0; j <= vcnt; j++)
  109.     {
  110.       #ifndef NDEBUG
  111.         printf("%ld. Stelle: %ld\n",ecnt-1,temp[j]);
  112.       #endif
  113.       result[ecnt] = temp[j];
  114.       ecnt++;
  115.       temp[j] = 0;
  116.     };
  117.     vcnt = 0;
  118.     temp[0] = 0;
  119.       }
  120.     };
  121.   };
  122. }
  123.  
  124. int main (void)
  125. {
  126.   clock_t timestart,timeend;
  127.   printf("Berechnung von PI\n");
  128.   for (;;)
  129.   {
  130.     printf("Stellenanzahl (0 für Ende):");
  131.     scanf("%ld",&n);
  132.     if (n < 1)
  133.       exit(0);
  134.     klen = (n * 10) / 3;
  135.     result = (int *) malloc(n*sizeof(int));
  136.     chain = (int *) malloc(klen*sizeof(int));
  137.     temp = (int *) malloc(n*sizeof(int));
  138.     if (result == NULL || chain == NULL || temp == NULL)
  139.     {
  140.       printf("no memory, no pi.\n");
  141.       exit(100);
  142.     };
  143.     init_chain();
  144.     timestart = clock();
  145.     drop();
  146.     timeend = clock();
  147.     printf("Zeitbedarf für %ld Stellen: %lds\n",n,(timeend-timestart) / CLOCKS_PER_SEC);
  148.     write_result();
  149.     free(result);
  150.     free(chain);
  151.     free(temp);
  152.   };
  153. return NULL;
  154. }
  155.